#pragma once
#include"Common.h"
#include"ObjectPool.h"
// 一层基数树（直接哈希）
template <int BITS>
class TCMalloc_PageMap1 {
private:
	static const int LENGTH = 1 << BITS;//页数目，BITS是存储页号需要多少位，假设一页8K=2^13；32位下存储页号需要=(32-13)=19位
	void** array_;//指针数组
public:
	typedef uintptr_t Number;
	explicit TCMalloc_PageMap1( ) {
		size_t bytes = sizeof(void*) << BITS;//需要开辟的字节数
		size_t alignSize = AMSize::_RoundUp(bytes, 1 << PAGE_SHIFT);//bytes>2^18（256*1024），按页大小对齐
		array_ = (void**)SystemAlloc(alignSize >> PAGE_SHIFT);//按页分配内存

		memset(array_, 0, sizeof(void*) << BITS);
	}

	//返回映射值
	void* get(Number k) const {
		if ((k >> BITS) > 0) {//页号不在页数目范围
			return NULL;
		}
		return array_[k];
	}

	//建立映射
	void set(Number k, void* v) {
		array_[k] = v;
	}
};
//二层基数树（分层哈希）
template <int BITS>
class TCMalloc_PageMap2 {
private:
	static const int ROOT_BITS = 5;//前5个比特位
	static const int ROOT_LENGTH = 1 << ROOT_BITS;//2^5第一层存储元素个数
	static const int LEAF_BITS = BITS - ROOT_BITS;//19-5=14,剩下14个比特位
	static const int LEAF_LENGTH = 1 << LEAF_BITS;//2^14第二层存储元素个数
	// Leaf node
	struct Leaf {
		void* values[LEAF_LENGTH];//2^5  * 4 =2^7大小
	};
	Leaf* root_[ROOT_LENGTH];
public:
	typedef uintptr_t Number;
	explicit TCMalloc_PageMap2( ) {	
		memset(root_, 0, sizeof(root_));//第一层空间清理
		PreallocateMoreMemory();
	}
	void* get(Number k) const {
		const Number i1 = k >> LEAF_BITS;//k低19位存储页号（合法的高位都是0），右移14位，获取19位中的前5位（[18,14]）确定第一层的下标
		const Number i2 = k & (LEAF_LENGTH - 1);//获取后13位与k与运算获得第二层的下标
		if ((k >> BITS) > 0 || root_[i1] == NULL)// 页号值超过范围或者页号映射的空间未开辟
		{
			return NULL;
		}
		return root_[i1]->values[i2];//返回映射的span指针
	}
	void set(Number k, void* v) {
		const Number i1 = k >> LEAF_BITS;
		const Number i2 = k & (LEAF_LENGTH - 1);
		assert(i1 < ROOT_LENGTH);
		root_[i1]->values[i2] = v;//建立映射
	}
	bool Ensure(Number start, size_t n) {
		for (Number key = start; key <= start + n - 1;) {
			const Number i1 = key >> LEAF_BITS;
			// 检查是否超出第一层下标范围
			if (i1 >= ROOT_LENGTH)
				return false;
			// 开辟空间
			if (root_[i1] == NULL)//第一层i1指向的空间未开辟 
			{
				static ObjectPool<Leaf>LeafPool;
				Leaf* leaf = (Leaf*)LeafPool.New();
				memset(leaf, 0, sizeof(*leaf));
				root_[i1] = leaf;
			}
			//推进叶节点的地址
			key = ((key >> LEAF_BITS) + 1) << LEAF_BITS;//移到下一页空间首地址
		}
		return true;
	}
	void PreallocateMoreMemory() {
		//将第二层空间全部开好
		Ensure(0, 1 << BITS);
	}
};
// 三层基数树
template <int BITS>
class TCMalloc_PageMap3 {
private:
	static const int INTERIOR_BITS = (BITS + 2) / 3; //第1、2层使用的比特位（17位），64位下，BITS=51,
	static const int INTERIOR_LENGTH = 1 << INTERIOR_BITS;//第1、2层存储个数

	static const int LEAF_BITS = BITS - 2 * INTERIOR_BITS;//第3层使用的比特位（17位）
	static const int LEAF_LENGTH = 1 << LEAF_BITS;//第3层存储个数
	// Interior node
	struct Node {
		Node* ptrs[INTERIOR_LENGTH];//1M大小，2^17  *  8 =2^20=1M
	};
	// Leaf node
	struct Leaf {
		void* values[LEAF_LENGTH];//1M大小，2^17  *  8 =2^20=1M
	};

	Node* NewNode() {
		//Node* result = reinterpret_cast<Node*>((*allocator_)(sizeof(Node)));
		static ObjectPool<Node>NodePool;
		Node* result = (Node*)NodePool.New();
		if (result != NULL) {
			memset(result, 0, sizeof(*result));
		}
		return result;
	}
	Node* root_;

public:
	typedef uintptr_t Number;
	explicit TCMalloc_PageMap3( ) {
		root_ = NewNode();
	}
	void* get(Number k) const {
		const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);//BITS51位中，前17位作第一层下标
		const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH - 1);//中间17位作第二层下标
		const Number i3 = k & (LEAF_LENGTH - 1);//后17位作第三层下标
		if ((k >> BITS) > 0 || root_->ptrs[i1] == NULL || root_->ptrs[i1]->ptrs[i2] == NULL) //页号超出范围或者页号映射的空间未开辟
		{
			return NULL;
		}
		return reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3];//获取映射的span
	}
	void set(Number k, void* v) {
		assert(k >> BITS == 0);
		const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);
		const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH - 1);
		const Number i3 = k & (LEAF_LENGTH - 1);
		reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3] = v;
	}
	bool Ensure(Number start, size_t n) {
		for (Number key = start; key <= start + n - 1;) {
			const Number i1 = key >> (LEAF_BITS + INTERIOR_BITS);//获取第一层下标
			const Number i2 = (key >> LEAF_BITS) & (INTERIOR_LENGTH - 1);//获取第二层下标
			// 检查下标合法性
			if (i1 >= INTERIOR_LENGTH || i2 >= INTERIOR_LENGTH)
				return false;
			// 开辟第二层空间
			if (root_->ptrs[i1] == NULL) {
				Node* n = NewNode();
				if (n == NULL) return false;
				root_->ptrs[i1] = n;
			}
			// 开辟第三层空间
			if (root_->ptrs[i1]->ptrs[i2] == NULL) {
				//Leaf* leaf = reinterpret_cast<Leaf*>((*allocator_)(sizeof(Leaf)));
				//if (leaf == NULL) return false;
				static ObjectPool<Leaf>LeafPool;
				Leaf* leaf = LeafPool.New();
				memset(leaf, 0, sizeof(*leaf));
				root_->ptrs[i1]->ptrs[i2] = reinterpret_cast<Node*>(leaf);
			}

			key = ((key >> LEAF_BITS) + 1) << LEAF_BITS; //移到下一页空间首地址
		}
		return true;
	}
	void PreallocateMoreMemory() 
	{}
};